package com.czk.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 希尔排序
 *
 * @Author:ChenZhangKun
 * @Date: 2020/6/28 21:12
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = {2, 5, 8, 4, 6, 2, 1, 3, 9, 10};
        shellSort(array);
        shellSort_move(array);
        // 测试bw个数据
        int[] array_1 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array_1[i] = new Random().nextInt(80000);
        }
        long l2 = System.currentTimeMillis();
        shellSort(array_1);
        long l3 = System.currentTimeMillis();
        System.out.println(l3 - l2);
        long l = System.currentTimeMillis();
        shellSort_move(array_1);
        long l1 = System.currentTimeMillis();
        System.out.println((l1 - l) / 1000);
    }

    /**
     * 希尔排序的交换法
     *
     * @param array
     */
    public static void shellSort(int[] array) {
        int temp;
        int m = 1;
        // 分组,分别一直往下
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 分组后先排序
            for (int i = gap; i < array.length; i++) {
                // 第一个与第六个比较，以此类推
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果比后面的大则交换位置
                    if (array[j] > array[j + gap]) {
                        temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
//            System.out.println("希尔排序第"+m+"轮  "+Arrays.toString(array));
//            m++;
        }
        //      System.out.println(Arrays.toString(array));
    }

    /**
     * 希尔排序的交换法
     *
     * @param array
     */
    public static void shellSort_move(int[] array) {
        int temp;
        int m = 1;
        // 分组,分别一直往下
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 分组后先排序
            for (int i = gap; i < array.length; i++) {
                // 临时变量
                int j = i;
                temp = array[j];
                if (array[j] < array[j - gap]) {
                    while (j - gap > 0 && array[j - gap] > temp) {
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    // 退出while，找到插入位置
                    array[j] = temp;
                }
            }
            // System.out.println("希尔排序第"+m+"轮  "+Arrays.toString(array));
            m++;
        }
        //System.out.println(Arrays.toString(array));
    }
}
